//给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。 
//
// 算法的时间复杂度应该为 O(log (m+n)) 。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums1 = [1,3], nums2 = [2]
//输出：2.00000
//解释：合并数组 = [1,2,3] ，中位数 2
// 
//
// 示例 2： 
//
// 
//输入：nums1 = [1,2], nums2 = [3,4]
//输出：2.50000
//解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
// 
//
// 
//
// 
//
// 提示： 
//
// 
// nums1.length == m 
// nums2.length == n 
// 0 <= m <= 1000 
// 0 <= n <= 1000 
// 1 <= m + n <= 2000 
// -10⁶ <= nums1[i], nums2[i] <= 10⁶ 
// 
//
// Related Topics 数组 二分查找 分治 👍 7167 👎 0


package LeetCode.editor.cn;


/**
 * @author ldltd
 * @date 2024-07-12 16:44:31
 * 4.寻找两个正序数组的中位数
 
 */
 
public class MedianOfTwoSortedArrays {
    public static void main(String[] args) {
    //测试代码
    MedianOfTwoSortedArrays fun = new MedianOfTwoSortedArrays();
    Solution solution= fun.new Solution();
    int[] nums1 = new int[]{};
    int[] nums2 = new int[]{2};
    System.out.println(solution.findMedianSortedArrays3(nums1, nums2));
    }

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    //朴素解法，归并到一个数组，时间复杂度M+N,空间复杂度m+n
    public double findMedianSortedArrays1(int[] nums1, int[] nums2) {
        int[] tem;
        int m = nums1.length;
        int n = nums2.length;
        tem = new int[m + n];
        if (m == 0) {
            return (nums2[(n + 1) / 2] + nums2[n / 2 + 1]) / 2;
        }
        if (n == 0) {
            return (nums1[(m + 1) / 2] + nums1[n / 2 + 1]) / 2;
        }
        int count = 0, i = 0, j = 0;
        while (count != m + n) {
            if (i == m) {
                while (j != n) {
                    tem[count++] = nums2[j++];
                }
                break;
            }
            if (j == n) {
                while (i != m) {
                    tem[count++] = nums1[i++];
                }
                break;
            }
            if (nums1[i] < nums2[j]) {
                tem[count++] = nums1[i++];
            } else {
                tem[count++] = nums2[j++];
            }
        }
        return (tem[(count + 1) / 2 - 1] + tem[count / 2]) / 2;
    }


    /*不开辟空间
     * 需要第（m+n+1）/2 -1和(m+n)/2个数,从0开始计数
     * 时间复杂度依旧是 O(m+n)
     * 空间复杂度是 O(1）
     * */
    public double findMedianSortedArrays2(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int len = m + n;
        //奇数，直接返回res，t保存上一个位置的结果
        int res = -1, t = -1;
        //记录两个数组运行到的位置
        int a = 0, b = 0;
        //遍历到中间的位置
        for (int i = 0; i <= len / 2; i++) {
            t = res;
            if (a < m && (b >= n || nums1[a] < nums2[b])) {
                res = nums1[a++];
            } else {
                res = nums2[b++];
            }
        }
        if ((len & 1) == 0) {
            return (t + res) / 2.0;
        } else {
            return res;
        }
    }
    /*
    * 时间复杂度：每进行一次循环，我们就减少 k/2 个元素，所以时间复杂度是 O(log(k)，而 k=(m+n)/2，所以最终的复杂也就是 O(log(m+n))
    空间复杂度： O(1)。
    * 对于m+n中的第k个，当m+n是奇数时，中位数是(m+n)/2，当是偶数时为(m+n)/2和(m+n/2)+1的平均值
    *只需要找出(m+n+1)/2大的数和第(m+n+2)/2大的数，然后求平均数即可
    * 我们比较两个数组A,B的第 k/2 -1 个数字，如果 k 是奇数，向下取整
    * 两者中的小值，最多有第一个前面的k/2-1+k/2+1个数比他小，即k-2
    * 就表明该数组的前 k/2 个数字都不是第 k 小数字，所以可以排除。
    * 如果两个数相等，任取一个不是
    * 为了防止数组长度小于 k/2，所以每次比较 min(k/2，len(数组) 对应的数字，
    * 把小的那个对应的数组的数字排除，将两个新数组进入递归，
    * 并且 k 要减去排除的数字的个数。递归出口就是当 k=1 或者其中一个数组长度是 0 了
    */
    public double findMedianSortedArrays3(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int len = m + n;
        int l=(len+1)/2;
        int r=(len+2)/2;
        return (getKth(nums1,0,m-1,nums2,0,n-1,l)+getKth(nums1,0,m-1,nums2,0,n-1,r))*0.5;
    }
    //分别找出第(m+n+1)/2和(m+n+2)/2个数（指顺序而不是坐标）
    private double getKth(int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int k){
        //计算两个数组的长度
        int len1=end1 - start1 +1;
        int len2 = end2 - start2+1;
        //让len1的长度始终小于len2，保证空的数组一定是len1
        if(len1>len2) return getKth(nums2,start2,end2,nums1,start1,end1,k);
        //空的时候
        if(len1==0) return nums2[start2+k-1];
        //最后的情况，终止条件
        if(k==1) return  Math.min(nums1[start1],nums2[start2]);
        //比较位置的数
        int i=start1+Math.min(len1,k/2)-1;
        int j=start2+Math.min(len2,k/2)-1;
        //排除掉小于的，那个数组的前面几个数
        if(nums1[i]>nums2[j]){
            //排除j部分区间，同时更新k
            return getKth(nums1,start1,end1,nums2,j+1,end2,k-(j-start2+1));
        }else {
            return getKth(nums1,i+1,end1,nums2,start2,end2,k-(i-start1+1));
        }
    }

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m=nums1.length;
        int n=nums2.length;
        int len=m+n;
        int l=(len+1)/2-1;
        int r=(len)/2;
        return (getK(nums1,0,m-1,nums2,0,n-1,l)+getK(nums1,0,m-1,nums2,0,n-1,r))*0.5;
    }
    public  double getK(int[] nums1,int start1,int end1,int[] nums2,int start2,int end2,int k){
         int len1=end1-start1+1;
         int len2=end2-start2+1;
        if(len1>len2) return getK(nums2,start2,end2,nums1,start1,end1,k);

        if(len1==0) return nums2[start2+k];
         if(k==0) return Math.min(nums1[start1],nums2[start2]);
         int i=start1+Math.min(len1,(k+1)/2)-1;
         int j=start2+Math.min(len2,(k+1)/2)-1;
         if(nums1[i]>nums2[j]){
             return getK(nums1,start1,end1,nums2,j+1,end2,k-(j-start2+1));
         }else {
             return getK(nums1,i+1,end1,nums2,start2,end2,k-(i-start1+1));
         }
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
